#include <iostream>
#include <string>
#include <stack>
using namespace std;

int calculate(string s)
{
    int res = 0, num = 0, sign = 1;
    stack<int> st;
    for (int i = 0; i < s.size(); i++)
    {
        char c = s[i];
        if (isdigit(c))
            num = num * 10 + (c - '0');
        else if (c == '+' || c == '-')
        {
            res += sign * num;
            num = 0;
            sign = (c == '+' ? 1 : -1);
        }
        else if (c == '(')
        {
            // 遇到左括号，要先把之前的值和符号入栈,这个符号是 括号内 计算结果的符号
            st.push(res);
            st.push(sign);
            res = 0;
            sign = 1;
        }
        else if (c == ')')
        {
            res += sign * num; // 把括号里面的值计算完毕
            num = 0;
            res *= st.top();
            st.pop();
            res += st.top();
            st.pop();
        }
        if (i == s.size() - 1)
        {
            res += sign * num;
        }
    }
    return res;
}

// 每次遇到括号，就递归进入函数计算这个括号里面的内容然后返回出去
int calCore(string &s, int &i)
{
    stack<int> st;   // 维护每一位数字
    char sign = '+'; // 记录 num 前的符号，初始化为 +
    int num = 0;
    for (; i < s.size(); i++)
    {
        // char c = s[i];for循环中不应该用c,直接用S[i]才能得到准确的结果,因为递归之后,往前推进了.
        if (isdigit(s[i])) // 如果是数字，连续读取到 num
            num = num * 10 + (s[i] - '0');
        if (s[i] == '(')
        {
            i++; // 跳过 (
            num = calCore(s, i);
            i++; // 跳过 )
        }

        // 如果不是数字，就是遇到了下一个符号，
        // 之前的数字和符号就要存进栈中
        if ((!isdigit(s[i]) && s[i] != ' ') || i == s.size() - 1) // 走到最后一位数也需要进来处理
        {
            switch (sign) //
            {
                int prev;
            case '+':
                st.push(num);
                break;
            case '-':
                st.push(-num);
                break;
            case '*': // 乘法和除法的优先级就体现在能够和top运算
                prev = st.top();
                st.pop();
                st.push(prev * num);
                break;
            case '/':
                prev = st.top();
                st.pop();
                st.push(prev / num);
                break;
            }

            if (s[i] == ')') // 递归过程才会遇到右括号,
                break;
            // 更新符号为当前符号，数字清零
            sign = s[i];
            num = 0;
        }
    }
    // 将栈中所有结果求和就是答案
    int ret = 0;
    while (!st.empty())
    {
        ret += st.top();
        st.pop();
    }
    return ret;
}
// 递归写法,改写法可以解决乘除问题
int calculate1(string s)
{
    int i = 0;
    return calCore(s, i);
}